package com.icbc.DataStructuresAndAlgorithms;

import org.junit.Test;

import java.util.Arrays;

public class KMPDomo {
	public static void main(String[] args) {
		String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
		String str2 = "尚硅谷你尚硅你";
		int baoli = baoli(str1, str2);
		System.out.println(baoli);
	}
	
	@Test
	public void test(){
		String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
		String str2 = "尚硅谷你尚硅你";
		System.out.println(Arrays.toString(KMPNext(str2)));
		System.out.println(KMPSerch(str1, str2, KMPNext(str2)));
	}
	
	//暴力匹配算法1
	public static int baoli(String str1,String str2){
		char[] chars = str1.toCharArray();
		char[] chars1 = str2.toCharArray();
		for (int i = 0; i < chars.length ; i ++){
			if (chars[i] == chars1[0]) {
				boolean flag = true;
				for (int j = 1 ; j < chars1.length ; j ++){
					if (chars[i + j] != chars1[j]){
						flag = false;
						break;
					}
				}
				if (flag){
					return i;
				}
			}
		}
		return -1;
	}
	
	//暴力匹配算法2
	public static int baoli2(String str1,String str2){
		char[] s1 = str1.toCharArray();
		char[] s2 = str2.toCharArray();
		
		int s1Len = s1.length;
		int s2Len = s2.length;
		
		int i = 0;
		int j = 0;
		while (i < s1Len && j < s2Len){
			if (s1[i] == s2[j]){
				i ++;
				j ++;
			} else {
				i = i - (j - 1);
				j = 0;
			}
		}
		if (j == s2Len){
			return i - j;
		} else {
			return -1;
		}
	}
	
	//根据目标字符串获取部分匹配值表
	public static int[] KMPNext(String str){
		char[] chars = str.toCharArray();
		//创建一个数组保存匹配值表
		int[] next = new int[chars.length];
		//头一个字符的匹配值一定为0
		next[0] = 0;
		//循环
		for (int i = 1 , j = 0; i < chars.length; i++) {
			//当str.charAt(i) != str.charAt(j)时,我们需要从next[j - 1]中获取最新的j
			//直到我们发现str.charAt(i) == str.charAt(j)成立时,才会退出
			while (j > 0 && chars[i] != chars[j]) {
				j = next[j - 1];
			}
			//当str.charAt(i) == str.charAt(j)时,部分匹配值+1
			if (chars[i] == chars[j]) {
				j++;
			}
			next[i] = j;
		}
		return next;
	}
	
	//KMP算法匹配字符串
	public static int KMPSerch(String str1,String str2,int[] next){
		
		for (int i = 0,j = 0; i < str1.length(); i++) {
			//kmp算法的核心代码,下面判断了相等的情况,但没有判断不等的情况
			while (j > 0 && str1.charAt(i) != str2.charAt(j)){
				j = next[j - 1];
			}
			//当str.charAt(i) == str.charAt(j)时,继续验证下一个字符是否相等
			if (str1.charAt(i) == str2.charAt(j)){
				j ++;
			}
			/*
			 * 当j的值达到目标字符串长度时,表示找到了该子串,
			 * 返回位置,因为在上面j进行了++,而i还未进行++
			 * 所以使用i - j + 1
			 */
			if (j == next.length){
				return i - j + 1;
			}
		}
		return -1;
	}
}
